# coding=utf-8

"""
找到链表中环开始的结点

思路和判断是不是存在环 是一样的
1   使用一个数组保存所有的值，当访问某一个结点的时候
    其下一个结点中的值已经存在于 vals 数组中则当前结点就是
    循环开始时候的结点

2   使用快慢指针的时候 两指针 同时指向的一个结点就是 循环开始的元素
"""


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def print_list(l):
    if l is None:
        print None

    while l.next is not None:
        l = l.next
        print l.val


class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode

        使用 hash 的版本

        为啥一直 TLE ????
        """

        vals = []
        l = head
        while l is not None:
            if l.next is None:
                return None

            elif l.next.val in vals:
                return l.val

            vals.append(l.val)
            l = l.next

        return None

    def detectCycle2(self, head):
        """使用快慢指针"""

        fast = head
        slow = head

        while fast is not None and slow is not None:
            if fast.val == slow.val:
                return fast.val

            if fast.next is None:
                fast = fast.next.next
            else:
                return None

            slow = slow.next

        return None


if __name__ == "__main__":
    sol = Solution()

    l1 = ListNode(1)
    _l1 = l1
    # l1.next = _l1

    # print(sol.detectCycle2(_l1))
    print_list(_l1)
